package cn.com.yang.datastruct.wgraph;

/**
 * 优先级队列
 * TODO
 * @author yangyijin
 * @since 2024年2月8日-上午9:17:15
 */
public class PriorityQueue {
	private Edge[] edges;//有序数组，从大到小
	private final int MAX_SIZE=20;
	private int size;//保存的边的条数
	
	public PriorityQueue() {
		edges = new Edge[MAX_SIZE];
		size=0;
	}
	/**
	 * 从大到小插入
	 * @param edge
	 */
	public void insert(Edge edge) {
		int i;
		for(i=0;i<size;i++) {
			if(edge.price >=edges[i].price) {
				break;
			}
		}
		//循环结束后就找到了i的位置，数组中的i和i后面的元素后移动
		for(int j=size-1;j>=i;j--) {
			edges[j+1]=edges[j];
		}
		//循环结束，i的位置空起来
		edges[i]=edge;//保证是从大到小的顺序
		size++;
	}
	
	/**
	 * 删除并得到最小的边
	 * @return
	 */
	public Edge removeMin() {
		return edges[--size];
	}
	/**
	 * 删除指定下标的边
	 * @param n
	 */
	public void removeN(int n) {
		for(int i=n;i<size;i++) {
			edges[i]=edges[i+1];
		}
		size--;
	}
	/**
	 * 获取最小的边，不删除
	 * @return
	 */
	public Edge peekMin() {
		return edges[size-1];
	}
	/**
	 * 判断队列是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return size ==0;
	}
	/**
	 * 获取元素边个数
	 * @return
	 */
	public int getSize() {
		return size;
	}
	/**
	 * 获取指定下标的边
	 */
	public Edge peekN(int N) {
		return edges[N];
	}
}
